﻿#define _CRT_SECURE_NO_WARNINGS 1
/* 队列 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>


typedef int QDataType;
// 定义队列的结构
typedef struct QueueNode
{
	QDataType _data;
	struct QueueNode* _next;
}QNode;
typedef struct Queue
{
	QNode* _phead;
	QNode* _ptail;
	int size;
}Queue;


void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType data);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);


// 初始化和销毁
void QueueInit(Queue* pq)
{
	assert(pq);
	QNode* head = (QNode*)malloc(sizeof(QNode));
	if (head == NULL)
	{
		printf("malloc failed!\n");
		exit(-1);
	}
	head->_next = NULL;
	pq->_phead = pq->_ptail = head;
	pq->size = 0;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->_phead->_next;
	QNode* next = NULL;
	while (cur)
	{
		next = cur->_next;
		free(cur);
		cur = next;
	}
	//销毁头节点
	free(pq->_phead);
	pq->_phead = pq->_ptail = NULL;
	pq->size = 0;
}

// 入队和出队
void QueuePush(Queue* pq, QDataType data)
{
	assert(pq);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		printf("malloc failed!\n");
		exit(-1);
	}
	newNode->_data = data;
	newNode->_next = NULL;
	
	pq->_ptail->_next = newNode;
	pq->_ptail = newNode;
	++pq->size;
}

void QueuePop(Queue* pq)
{
	assert(pq);
	// 只有一个头节点
	if (pq->_phead == pq->_ptail)
	{
		return;
	}

	QNode* del = pq->_phead->_next;
	pq->_phead->_next = del->_next;
	// 只有一个节点
	if (del == pq->_ptail)
	{
		pq->_ptail = pq->_phead;
	}
	free(del);
	del = NULL;
	--pq->size;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->_phead->_next);

	return pq->_phead->_next->_data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->_phead != pq->_ptail);
	return pq->_ptail->_data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->_phead == pq->_ptail;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}


void test()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	printf("size: %d\n", QueueSize(&q));
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\nsize: %d\n", QueueSize(&q));
	 //QueuePop(&q);
	QueuePush(&q, 6);
	QueuePush(&q, 7);
	QueuePush(&q, 8);
	QueuePush(&q, 9);
	QueuePush(&q, 10);
	printf("\nsize: %d\n", QueueSize(&q));
	printf("\n%d\n", QueueFront(&q));
	printf("\n%d\n", QueueBack(&q));
	if (!QueueEmpty(&q))
		printf("NO NULL\n");
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
		printf("\nsize: %d\n", QueueSize(&q));
	}
	if (QueueEmpty(&q))
		printf("\nNULL\n");
	else
		printf("NO NULL\n");
	printf("\nsize: %d\n", QueueSize(&q));

	QueueDestroy(&q);
}

int main()
{
	test();

	return 0;
}

